package com.zjsru.plan2023.oneday.oneDay202301;

/**
 * @Author: CookLee
 * @Date: 2023/1/28
 * 生成平衡数组的方案数
 *
 * 输入：nums = [2,1,6,4]
 * 输出：1
 * 解释：
 * 删除下标 0 ：[1,6,4] -> 偶数元素下标为：1 + 4 = 5 。奇数元素下标为：6 。不平衡。
 * 删除下标 1 ：[2,6,4] -> 偶数元素下标为：2 + 4 = 6 。奇数元素下标为：6 。平衡。
 * 删除下标 2 ：[2,1,4] -> 偶数元素下标为：2 + 4 = 6 。奇数元素下标为：1 。不平衡。
 * 删除下标 3 ：[2,1,6] -> 偶数元素下标为：2 + 6 = 8 。奇数元素下标为：1 。不平衡。
 * 只有一种让剩余数组成为平衡数组的方案。
 *
 */
public class WaysToMakeFair {
    
    /**
     * 动态规划
     * Odd 表示 所有奇数位置元素的和，even表示所有偶数位置元素的和，
     *
     *
     * @param nums 数组
     * @return int
     */
    public int waysToMakeFair(int[] nums) {
        int odd1 = 0, even1 = 0;
        int odd2 = 0, even2 = 0;
        for (int i = 0; i < nums.length; i++) {
            if ((i & 1) != 0) {
                odd2 += nums[i];
            } else {
                even2 += nums[i];
            }
        }
        int res = 0;
        //下标 i 之后的奇数下标元素会成为偶数下标元素，偶数下标元素会成为奇数下标元素。
        //所以删除后数组中全部奇数下标元素和为 odd1[i]+even2[i]，
        // 全部偶数下标元素和为 even2[i]+odd1[i]，若两者相等则说明删除下标 i 后的数组
        
        for (int i = 0; i < nums.length; i++) {
            if ((i & 1) != 0) {
                odd2 -= nums[i];
            } else {
                even2 -= nums[i];
            }
            if (odd2 + even1 == odd1 + even2) {
                res++;
            }
            //1号数组存储被2号数组弹出的奇偶数
            if ((i & 1) != 0) {
                odd1 += nums[i];
            } else {
                even1 += nums[i];
            }
        }
        return res;
    }
    
    public static void main(String[] args) {
        WaysToMakeFair waysToMakeFair = new WaysToMakeFair();
        int[] nums = new int[] {2, 1, 6, 4};
        System.out.println(waysToMakeFair.waysToMakeFair(nums));
    }
}
